package offer;
import java.util.PriorityQueue;
import java.util.Comparator;
import java.util.Queue;
public class  Offer41 {
//    public class StreamMedian {
//        PriorityQueue<Integer> minHeap = new PriorityQueue<Integer>(); //小顶堆，默认容量为11
//        PriorityQueue<Integer> maxHeap = new PriorityQueue<Integer>(11,new Comparator<Integer>(){ //大顶堆，容量11
//            public int compare(Integer i1,Integer i2){
//                return i2-i1;
//            }
//        });
//
//        public void Insert(Integer num) {
//            if(((minHeap.size()+maxHeap.size())&1)==0){//偶数时,下个数字加入小顶堆
//                if(!maxHeap.isEmpty() && maxHeap.peek()>num){
//                    maxHeap.offer(num);
//                    num=maxHeap.poll();
//                }
//                minHeap.offer(num);
//            }else{//奇数时，下一个数字放入大顶堆
//                if(!minHeap.isEmpty() && minHeap.peek()<num){
//                    minHeap.offer(num);
//                    num=minHeap.poll();
//                }
//                maxHeap.offer(num);
//            }
//        }
//
//        public Double GetMedian() {
//            if((minHeap.size()+maxHeap.size())==0)
//                throw new RuntimeException();
//            double median;
//            if((minHeap.size()+maxHeap.size()&1)==0){
//                median=(maxHeap.peek()+minHeap.peek())/2.0;
//            }else{
//                median=minHeap.peek();
//            }
//            return median;
//        }
//    }
static class MedianFinder {
    Queue<Integer> A, B;
    public MedianFinder() {
        A = new PriorityQueue<>(); // 小顶堆，保存较大的一半
        B = new PriorityQueue<>((x, y) -> (y - x)); // 大顶堆，保存较小的一半
    }
    public void addNum(int num) {
        if (A.size() != B.size()) {
            A.add(num);
            B.add(A.poll());
        } else {
            B.add(num);
            A.add(B.poll());
        }
    }
    public double findMedian() {
        return A.size() != B.size() ? A.peek() : (A.peek() + B.peek()) / 2.0;
    }
}
    public static void main(String[] args) {
        MedianFinder medianFinder = new MedianFinder();
        medianFinder.addNum(2);
        medianFinder.addNum(1);
        medianFinder.addNum(4);
        medianFinder.addNum(5);
        System.out.println(medianFinder.findMedian());
    }
}
